package leetcode.D100.T49;

import java.util.*;

class Solution {
   /*// 解法一：哈希+排序，时间复杂度O(nklogk)，空间复杂度O(nk)
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chs = str.toCharArray();
            Arrays.sort(chs);
            String key = String.valueOf(chs);
            if(!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(str);
        }
        return new ArrayList<List<String>>(map.values());
    }*/
    // 解法二：哈希+计数，时间复杂度O(nk)，空间复杂度O(nk)
   /*public List<List<String>> groupAnagrams(String[] strs) {
       Map<String, List<String>> map = new HashMap<>();
       int[] counts = new int[26];
       for(String str : strs) {
           Arrays.fill(counts, 0);
           for(int i=0; i<str.length(); ++i) {
               counts[str.charAt(i)-'a']++;
           }
           StringBuilder sb = new StringBuilder();
           for(int i=0; i<26; ++i) {
               sb.append(counts[i] + 'a');
           }
           String key = sb.toString();
           if(!map.containsKey(key)) {
               map.put(key, new ArrayList<>());
           }
           map.get(key).add(str);
       }
       return new ArrayList<>(map.values());
   }*/

    // 二刷
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        int[] cnt = new int[26];
        for (String str : strs) {
            Arrays.fill(cnt, 0);
            for (int i=0; i<str.length(); ++i)
                cnt[str.charAt(i)-'a']++;
            StringBuilder sb = new StringBuilder();
            for (int i=0; i<26; ++i) {
                sb.append(cnt[i]);
                sb.append(i + 'a');
            }
            String key = sb.toString();
            if (!map.containsKey(key))
                map.put(key, new ArrayList<>());
            map.get(key).add(str);
        }
        return new ArrayList<>(map.values());
    }
}
